/**
 * 题目：
 * 有 n 件物品，
 * 物品体积用一个名为 w 的数组存起来，
 * 物品的价值用一个名为 value 的数组存起来；
 * 每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。
 * 现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？
 *
 * 注意： 每种物品都只有1件
 */

/**
 * 思路分析： 
 * 遇到最值问题，一定要在可能的解题方案中给动态优化留下一席之地。
 * 事实上，背包系列问题，正是动态规划的标准对口问题。
 * 
 * 首先应该确定状态转移方程
 * 倒推，假设容量到了c，f(i, c)表示前i件物品装入容量为c的背包中获得的价值最大，
 * 第i件物品的可能性有：在背包，或者不在背包，所以有如下方程
 * f(i, c) = f(i - 1, c)
 * f(i, c) = f(i - 1, c- w[i]) + value[i]
 * 我们只需要比较两者的最大值即可
 * 自变量是物品的索引i和体积v，因变量是总价值，我们用一个二维数组将关系编码化
 * dp[i][v] = Math.max(dp[i-1][v], dp[i-1][v-w[i]]+ c[i])
 * 以上就是状态转移方程
 * 
 * 我们用一个双重循环来处理
 * for(let i=1;i<=n;i++) {
    for(let v=w[i]; v<=c;v++) {
      dp[i][v] = Math.max(dp[i-1][v], dp[i-1][v-w[i]]+value[i])
    }
   }
 * 
   在时间复杂度上，为On，但是空间复杂度上，我们记录了很多冗余数据，对于第i行数据，
   我们只关系i-1行的数据
 */

/**
 * 滚动数组
 * 固定一块存储空间，滚动更新这块存储空间的内容，确保每个时刻空间内的数据
 * 是当前真正会用到的最新数据，从而达到节约内存的效果，这个手段就是滚动数组
 *
 * 我们用滚动数组来优化状态转移方程，从而降低空间复杂度
 */

// 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
function knapsack(n, c, w, value) {
  // dp是动态规划的状态保存数组
  const dp = new Array(c + 1).fill(0);
  // res 用来记录所有组合方案中的最大值
  let res = -Infinity;
  for (let i = 1; i <= n; i++) {
    for (let v = c; v >= w[i]; v--) {
      // 写出状态转移方程
      dp[v] = Math.max(dp[v], dp[v - w[i]] + value[i]);
      // 即时更新最大值
      if (dp[v] > res) {
        res = dp[v];
      }
    }
  }
  return res;
}
/**
 * 有一个载重量是10kg 的背包，有五个物品，a 2kg 6元，b 2kg 3元，c 6kg 5元，
 * d 5kg 4元，e 4kg 6元。
 * 问怎么放物品，价值最高？
 */
let n = 5
let c = 10
let w = [2, 2, 6, 5, 4]
let value = [6, 3, 5, 4, 6]
console.log(knapsack(n, c, w, value));
